package main

// 每一步都使用 临时的 数组去代替，模拟过程直到剩最后一个元素
// 将删掉的过程变换一下，得到每一步需要的
// 这种写法会出现问题， 第3375个测试用例过不去！！ 会提示
// runtime: out of memory: cannot allocate 209715200-byte block (335282176 in use)
// fatal error: out of memory
// runtime.throw(0x4f0f52, 0xd)
// 太长了，内存分配不足
func lastRemaining(n int) int {
	rst := make([]int, n)
	for i := 1; i <= n; i++ {
		rst = append(rst, i)
	}
	// fmt.Println(rst)
	flag := true
	for len(rst) > 1 {
		temp := make([]int, 0)
		// 左
		if flag {
			for i := 1; i < len(rst); i += 2 {
				temp = append(temp, rst[i])
			}
			flag = false
			// fmt.Println(temp)
		} else { // 右：将逆序 转换为正序
			n := len(rst)
			// 偶数个
			if n%2 == 0 {
				for i := 0; i < len(rst); i += 2 {
					temp = append(temp, rst[i])
				}
			} else { // 奇数
				for i := 1; i < len(rst); i += 2 {
					temp = append(temp, rst[i])
				}
			}
			flag = true
			// fmt.Println(temp)
		}
		rst = temp
	}
	return rst[0]
}

// 使用三个变量代替数组表示， 本质上是一个 等差数列。所以
// left， right， 表示左右边界， step 表示跳数。  这三个变量就能代替数组存储。
// 然后根据题目意思， 不断更新 left， right， step。维持新的“数组”
// 当 left == right 时，说明只有一个元素了， 为了方便，还可以定义一个 cnt，表示当前等差数列的元素个数。
// 按照题目规律， 每次选出下一轮的等差数列
func lastRemaining(n int) int {
	left, cnt, right := 1, n, n
	// 等差数列的 跳数
	step := 1
	// fmt.Println(rst)
	flag := true
	for cnt > 1 {
		// 左
		if flag {
			// 更新 left， right 和 cnt
			left = left + step
			if cnt%2 == 1 {
				right -= step
			}
			// 不管 元素个数为 奇数或者偶数， 最后都会为 cnt / 2 向下取整的一半。
			cnt = cnt / 2
			flag = false
			// fmt.Println(temp)
		} else { // 右：将逆序 转换为正序
			// 偶数个
			if cnt%2 == 0 {
				cnt = cnt / 2
				right -= step
			} else { // 奇数
				cnt = cnt / 2
				left += step
				right -= step
			}
			flag = true
			// fmt.Println(temp)
		}
		// 更新等差数列的间隔
		step *= 2
	}
	return right
}

// 还可以进行优化上面的代码， 逻辑清晰，代码可以写的更加简洁。
